iT邦幫忙

2023 iThome 鐵人賽

DAY 25
0

結果週日混一混就混過去了
沒刷啥題..好廢
重新振作一下
再來!

Find All Possible Recipes from Given Supplies

Q: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        List<String> result = new ArrayList<>();
        Map<String, Set<String>> ingredientsByRecipe = new HashMap<>();
        for (int i = 0;i < recipes.length;i++) {
            ingredientsByRecipe.put(recipes[i], new HashSet<>());
            for (int j = 0;j < ingredients.get(i).size();j++) {
                ingredientsByRecipe.get(recipes[i]).add(ingredients.get(i).get(j));
            }
        }
        
        Queue<String> q = new LinkedList<>();
        for (String supply : supplies) {
            q.offer(supply);
        }
        while(!q.isEmpty()) {
            String supply = q.poll();
            for (Map.Entry<String, Set<String>> entry : ingredientsByRecipe.entrySet()) {
                if (entry.getValue().size() != 0 && entry.getValue().contains(supply)) {
                    entry.getValue().remove(supply);
                    if (entry.getValue().size() == 0) {
                        q.offer(entry.getKey());
                        result.add(entry.getKey());
                    }
                }
            }
        }
        return result;
    }
}

Smallest Index With Equal Value

Q: https://leetcode.com/problems/smallest-index-with-equal-value/description/

class Solution {
    public int smallestEqual(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == i % 10) {
                return i;
            }
        }
        return -1;
    }
}

這在幹嘛??

Single-Row Keyboard

Q: https://leetcode.com/problems/single-row-keyboard/description/

class Solution {
    public int calculateTime(String keyboard, String word) {
        final Map<Character, Integer> indexByChar = new HashMap<>();
        for (int i = 0;i < keyboard.length();i++) {
            indexByChar.put(keyboard.charAt(i), i);
        }
        int sum = 0;
        int now = 0;
        for (int i = 0;i < word.length();i++) {
            sum += Math.abs(indexByChar.get(word.charAt(i)) - now);
            now = indexByChar.get(word.charAt(i));
        }
        return sum;
    }
}

Perfect Rectangle

Q: https://leetcode.com/problems/perfect-rectangle/description/

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles.length == 0 || rectangles[0].length == 0) return false;
        Set<String> points = new HashSet<String>();
        int area = 0;
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        int maxA = Integer.MIN_VALUE;
        int maxB = Integer.MIN_VALUE;
        for (int[] r : rectangles){
            int x = r[0];
            int y = r[1];
            int a = r[2];
            int b = r[3];
            area += (x-a) * (y-b);
            minX = Math.min(minX, x);
            minY = Math.min(minY, y);
            maxA = Math.max(maxA, a);
            maxB = Math.max(maxB, b);
            String bottomLeft = getHash(x,y);
            String topLeft = getHash(x,b);
            String bottomRight = getHash(a,y);
            String topRight = getHash(a,b);
            checkInSet(points, bottomLeft);
            checkInSet(points, topLeft);
            checkInSet(points, bottomRight);
            checkInSet(points, topRight);
        }
        String fullBottomLeft = getHash(minX,minY);
        String fullTopLeft = getHash(minX,maxB);
        String fullBottomRight = getHash(maxA,minY);
        String fullTopRight = getHash(maxA,maxB);
        if (points.size() != 4 || !points.contains(fullBottomLeft) 
            || !points.contains(fullTopLeft) || !points.contains(fullBottomRight) || !points.contains(fullTopRight)) return false;
        int fullArea = (minX-maxA) * (minY-maxB);
        return area == fullArea;
    }
    private void checkInSet(Set<String> points, String hash){
        if (!points.contains(hash)) {
            points.add(hash);
        } else { 
            points.remove(hash);
        }
    }
    private String getHash(int x, int y){
        return x + ":" + y;
    }
}

上一篇
09/24
下一篇
09/26
系列文
30天準備google面試30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言